// https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

/*
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。
*/

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
		int len = nums.size();
		int left = 0;
		int right = len - 1;

		while(left < right){ // 注意：这里是重点
			int mid = (left + right) / 2;
			if(nums[mid] > target){
				right = mid;
			}else if(nums[mid] < target){
				left = mid + 1; // 注意：这里是重点
			}else{
				left = mid;
				right = mid;
				while(left > 0 && nums[left] == nums[left - 1]){
					left--;
				}
				while(right < len - 1 && nums[right] == nums[right + 1]){
					right++;
				}
				return {left, right};
			}
		}
		// 注意：这里是重点，必须处理
		if(left == right && nums[left] == target){
			while(left > 0 && nums[left] == nums[left - 1]){
                left--;
            }
            while(right < len - 1 && nums[right] == nums[right + 1]){
                right++;
            }
            return {left, right};
		}
		return {-1, -1};
    }
};

int main(){
	vector<int> input = {1, 1, 2};
	int target = 1;
	Solution so;
	auto res = so.searchRange(input, target);
	cout << res[0] << "," << res[1] << endl;
	return 0;
}